//class Solution {
//public:
//    bool isValid(string s) {
//        stack<char> st;
//        for (auto ch : s)
//        {
//            if (ch == '(' || ch == '[' || ch == '{')
//                st.push(ch);
//            else
//            {
//                if (!st.empty() && ((ch == ')' && st.top() == '(')
//                    || (ch == ']' && st.top() == '[') || (ch == '}' && st.top() == '{')))
//                    st.pop();
//                else return false;
//            }
//        }
//        return st.empty();
//    }
//};



//class MyQueue {
//public:
//    MyQueue() {
//
//    }
//
//    void push(int x) {
//        PushSt.push(x);
//    }
//
//    int pop() {
//        int ret = peek();
//        PopSt.pop();
//        return ret;
//    }
//
//    int peek() {
//        if (PopSt.empty())
//        {
//            while (PushSt.size())
//            {
//                PopSt.push(PushSt.top());
//                PushSt.pop();
//            }
//        }
//        return PopSt.top();
//    }
//
//    bool empty() {
//        return PushSt.empty() && PopSt.empty();
//    }
//    stack<int> PushSt;
//    stack<int> PopSt;
//};




//class MyStack {
//public:
//    MyStack() {
//
//    }
//
//    void push(int x) {
//        if (q1.empty())
//            q2.push(x);
//        else
//            q1.push(x);
//    }
//
//    int pop() {
//        if (q1.empty())
//        {
//            while (q2.size() > 1)
//            {
//                q1.push(q2.front());
//                q2.pop();
//            }
//            int ret = q2.front();
//            q2.pop();
//            return ret;
//        }
//        else
//        {
//            while (q1.size() > 1)
//            {
//                q2.push(q1.front());
//                q1.pop();
//            }
//            int ret = q1.front();
//            q1.pop();
//            return ret;
//        }
//    }
//
//    int top() {
//        if (q1.empty()) return q2.back();
//        else return q1.back();
//    }
//
//    bool empty() {
//        return q1.empty() && q2.empty();
//    }
//    queue<int> q1;
//    queue<int> q2;
//
//};



class MyCircularQueue {
public:
    MyCircularQueue(int k) {
        arr = vector<int>(k + 1);
        rear = front = 0;
        capacity = k;
    }

    bool enQueue(int value) {
        if (isFull()) return false;
        else
        {
            arr[rear] = value;
            rear = (rear + 1) % (capacity + 1);
            return true;
        }
    }

    bool deQueue() {
        if (isEmpty()) return false;
        else
        {
            front = (front + 1) % (capacity + 1);
            return true;
        }
    }

    int Front() {
        return isEmpty() ? -1 : arr[front];
    }

    int Rear() {
        return isEmpty() ? -1 : arr[(rear + capacity) % (capacity + 1)];
    }

    bool isEmpty() {
        return front == rear;
    }

    bool isFull() {
        return (rear + 1) % (capacity + 1) == front;
    }
    vector<int> arr;
    int rear;
    int front;
    int capacity;
};